1. Technical Field
The invention disclosed broadly relates to data processing systems and more particularly relates to a system and method for high speed, pattern detection of serial data streams, using finite state machines.
2. Related Patent Applications
This patent application is related to the co-pending U.S. patent application Ser. No. 08/024,572, filed Mar. 1, 1993, now U.S. Pat. No. 5,375,070 entitled "Information Collection Architecture and Method for a Data Communications Network," by J. G. Waclawsky, Paul C. Hershey, Kenneth J. Barker and Charles S. Lingafelt, Sr., assigned to the IBM Corporation and incorporated herein by reference.
This patent application is also related to the co-pending U.S. patent application, Ser. No. 08/024,563, filed Mar. 1, 1993, now abandoned entitled "Event Driven Interface for a System for Monitoring and Controlling a Data Communications Network," by Paul C. Hershey, John G. Waclawsky, Kenneth J. Barker and Charles S. Lingafelt, Sr., assigned to the IBM Corporation and incorporated herein by reference.
This patent application is also related to the co-pending U.S. patent application, Ser. No. 08/024,542, filed Mar. 1, 1993, entitled "System and Method for Configuring an Event Driven Interface and Analyzing Its Output for Monitoring and Controlling a Data Communications Network," by John G. Waclawsky and Paul C. Hershey, assigned to the IBM Corporation and incorporated herein by reference.
This patent application is also related to the co-pending U.S. patent application, Ser. No. 08/138,045, filed Oct. 15, 1993, entitled "System and Method for Adaptive, Active Monitoring of a Serial Data Stream having a Characteristic Pattern," by Paul C. Hershey and John G. Waclawsky, assigned to the IBM Corporation and incorporated herein by reference.
3. Background Art
Finite state machines (FSM) are commonly used in the implementation of telecommunications protocols and of input/output processors, because finite state machines can define all possible conditions completely and unambiguously. However, a problem with finite state machines is defining the sequence of states and the accompanying actions to be accomplished with each state. Conventional implementations of finite state machines result in program code sets which are extensive and complex. This problem has been solved by the "System and Method for Adaptive, Active Monitoring of a Serial Data Stream having a Characteristic Pattern," by Paul C. Hershey, et al., cited above. The adaptive, active monitor comprises finite state machines (FSM) which are constructed to detect the occurrence of a characteristic data pattern in a bit stream. If the FSM successfully detects the pattern, it then outputs a pattern alarm signal, indicating the successful detection of the characteristic data pattern.
One feature of the adaptive, active monitor invention is the programmability of the finite state machines (FSMs) and the programmability of their interconnection. Each FSM consists of an address register and a memory. The address register has two portions, an n-1 bit wide first portion and a X-bit wide second portion X. X is one bit for binary data, X is a word of two bits for Manchester encoded data, or X is a word of five bits for FDDI encoded data. The X-bit wide portion is connected to the input data stream which contains the characteristic data pattern of interest. The n-X bit wide portion contains data which is output from the memory. The next address to be applied by the address register to the memory is made up of the X-1 bit wide portion and the next arriving X-bit word from the input data stream.
Each memory has a plurality of data storage locations, each having a first portion with n-X bits, to be output to the address register as part of the next address. Many of the memory locations have a second portion which stores a command to reset the address register if the FSM fails to detect its designated component bit pattern.
A terminal location in the memory of an FSM will include a start signal value to signal another FSM to start analyzing the data stream. If the terminal location in a predecessor FSM memory is successful in matching the last bit of its designated component bit pattern, then it will output a starting signal to a succeeding FSM. The succeeding FSM will begin analyzing the data stream for the next component bit pattern of the characteristic data pattern. The memory of an FSM can be a writable RAM, enabling its reconfiguration to detect different component bit patterns.
A remaining problem in the detection of characteristic data patterns in serial data streams is the need to perform complex pattern detection at the ultra high speeds of communications media operating at gigahertz clock frequencies. At these high frequencies, conventional high speed logic, such as emitter coupled logic (ECL,) is not sufficiently fast.